1. Field of the Invention
The invention relates generally to a method for storing and retrieving data in a memory cache system.
2. Description of Background
Data processing systems typically include a central processing unit (CPU) that executes instructions of a program stored in a main memory. To improve the memory response time, cache memories are used as high-speed buffers emulating the main memory. In general, a cache includes a directory to track stored memory addresses and a data array for storing data items present in the memory addresses. If a data item requested by the CPU is present in the cache, the requested data item is called a cache hit. If a data item requested by the CPU is not present in the cache the requested data item is called a cache miss.
The cache is usually smaller than the main memory, thereby limiting the amount of data that may be stored in the cache. To exploit temporal and spatial locality of data references, caches often store a most recently referenced data item, and store contiguous (in address) blocks of data items, respectively. The contiguous block of data items is referred as a cache line, and is the unit of transfer from the main memory to the cache. The choice of the number of bytes in a cache line is one parameter in a cache design. In a fixed size cache, a small line size, exploits temporal locality, and allows more unique lines to be stored, but increases the size of the directory. A large line size exploits spatial locality, but increases the amount of time needed to transfer the line from main memory to cache (a cache miss penalty), and limits the number of unique lines that can be resident in the cache at the same time.
Cache sectoring reduces the cache miss penalty. In cache sectoring, cache lines are divided into “sectors,” where the sector size is a function of a memory bus width. When a cache miss occurs, a cache line address is installed in a directory, but only the sector containing a referenced data item is transferred to a data array.
In sectored-caches, each directory entry maintains a “presence” bit per sector in the line. Presence bits are used to indicate which of the sectors in a line are present in the cache. Sectoring enables maintaining a small directory with a large line size without increasing the cache miss penalty. However, sectoring uses the data array inefficiently. For example, if a cache line is 32 bytes, and is made up of 4 byte sectors, there are 8 sectors in the cache line. If on average, only 3 out of the 8 sectors are referenced, 63% of the data array is “dead space.” which does not contain any useful data.